package midsearch;
/**
 * 题目 ：排序数组中只出现一次的数字
 * 题目详述 ：
 * 给定一个只包含整数的有序数组 nums，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 */
public class SingleNonDuplicate {
    /**
     * 核心思想：
     * 方法一 ：（对于所有数组元素进行两两匹配之后，进行二分查找）
     * （1）由于每个元素都会出现两次，同时只会有一个元素只会出现一次，即可以将num数组中的元素两两匹配，进行遍历；
     * 即，若是唯一元素出现的话，在其之前两两匹配的元素值相同；对比，在其之后，两两匹配的元素值不同。
     * （2）二分查找，若是当前两两匹配的元素相同的话，即唯一元素只可能出现在后半部分；
     * （3）若是两两匹配的元素不同的话，
     * a.即，需要去判断当前两两匹配的元素是否为第一个两两匹配元素值不同的，若是的话，即直接返回当前数组元素即可
     * （注意 : 首先，数组元素数目必然为奇数；其次，如何判断其是否为第一个，通过当前元素的前一组两两匹配元素是否相同来判断）；
     * b.即，若是当前元素的前一组两两匹配元素相同的话，那么就能够判断其为第一个两两匹配不相同的元素值；
     *
     *
     * 时间复杂度 ：由于使用了二分查找来进行查询 ：O（logn）；
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length / 2 ;
        while(start <= end){
            int middle = (start + end) / 2;
            int index = middle * 2;
            // 当start == end时，nums[index]所表示的是nums数组中的最后一个元素；
            // 也就是，代表着num[index + 1]已经超出了数组最大边界；
            // 即，需要对于当前遍历的数组元素是否存在进行判断
            if(index < nums.length - 1 && nums[index] != nums[index + 1]){ // 当前遍历的两两匹配元素值不相同
                // 同时满足：前一个两两匹配元素的元素值相同的话，即当前遍历的两两匹配元素值为第一个匹配值不同的；
                // 特殊情况 ： 即，当前遍历的两两匹配元素为整个num数组中的第一组的话，也是符合题目条件的；
                if(index == 0 || nums[index - 1] == nums[index - 2]){
                    return nums[index];
                }
                // 若是其不是第一组两两匹配元素值不同的，说明第一组两两匹配元素不同的在前半部分；
                end = middle - 1;
            }
            else {
                // 若是当前遍历的两两匹配元素值相同的话，说明唯一元素在后半部分；
                start = middle + 1;
            }
        }
        // 若是二分查找结束，还未能够找到唯一元素；
        // 即，只有一种情况会出现，由于数组元素数目是奇数的，
        // 对于最后一组单个元素，我们会选择对于其直接跳出二分查找，并未对其进行返回值；
        return nums[nums.length - 1];
    }

    /**
     * 方法二 ：暴力法
     * 即，就是由于两个相同元素之间的异或结果为零，同时 零与任何元素的异或结果，都是元素值本身；
     * 由于题目条件：只有一个唯一元素，同时其他元素都是两两重复出现；
     * ===》 无论数组是否排序好，直接对于数组中的所有元素进行异或，所得到的最终结果就是唯一元素的值
     *
     * 时间复杂度 ：O（n）
     */

    /**
     * 方法三 ：二分查找（直接对于数组中的所有元素进行二分查找）
     * 由于数组是排序好的数组，此种方法并不会去管 （除了唯一元素的其他元素重复次数，无论次数）
     */
//    public int singleNonDuplicate(int[] nums) {
//        int start = 0;
//        int end = nums.length - 1;
//        // 由于数组是排序数组，即可以使用二分查找；
//        while(start <= end){
//            int middle = (start + end) / 2;
//            // 即，特殊情况：遍历元素为数组first元素，由于其不存在前一个元素，所以单独列出来进行判断：其与后一个元素是否一致；
//            // 一般情况 ：即，在当前遍历元素不为数组首元素/数组尾元素的话，去判断当前元素是否与前后元素一致；
//            // 若是都不一致的话，直接返回遍历到的元素值即可（代表其为数组中唯一元素）；
//            // 一旦出现一致的话，那么就代表当前遍历的元素值不为数组nums中的唯一元素;
//            if((middle == 0 && nums[middle] != nums[middle + 1]) || (middle != 0 && middle != nums.length - 1
//                            && nums[middle] != nums[middle - 1] && nums[middle] != nums[middle + 1])){
//                return nums[middle];
//            }
//        }
//        return -1;
//    }
    /**
     * 注意 ：
     * 此种算法有问题 ：
     *      核心问题，在于获取到middle元素后，不知道该如何判断数组中的唯一元素存在于前半部分/后半部分；
     */
}
